package leetcode_100;

/**
 *@author 周杨
 *UniquePaths_62 走棋盘 只能向下或者向右走 
 *describe: 1 回溯法超时 2 动态规划解决 AC 87%
 *2018年5月10日 下午3:15:29
 */
public class UniquePaths_62 {
	int res=0;
	int x;
	int y;
	public static void main(String[] args) {
		UniquePaths_62 test=new UniquePaths_62();
		System.out.println(test.uniquePaths1(23, 12));//193536720

	}
	
	/**
	 * describe:典型的动态规划问题，对问题使用动态规划的方法进行求解。 
　　		用一个m*n的组数A保存结果。 
　　		对于A数组中的元素有。 
　　		1、当x=0或者y=0时有A[x][y] = 1； 
　　		2、当x>=1并且y>=1时有A[x][y] = A[x-1][y]+A[x][y-1]。 
　　		3、所求的结点就是A[m-1][n-1]。
	 * 2018年5月10日 下午3:16:50
	 */
	public int uniquePaths1(int m, int n) {
		int[][] result = new int[m][n];

        // 第一列的解
        for (int i = 0; i < m; i++) {
            result[i][0] = 1;
        }

        // 第一行的解    
        for (int i = 1; i < n; i++) {
            result[0][i] = 1;
        }

        // 其它位置的解
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                result[i][j] = result[i - 1][j] + result[i][j - 1];
            }
        }

        // 所求的解
        return result[m - 1][n - 1];
    }
	
	
	public int uniquePaths(int m, int n) {
		this.y=m;
		this.x=n;
		help(1,1);
        return this.res;
    }
	
	public void help(int x,int y) {
		if(x>this.x||y>this.y)
			return ;
		if(x==this.x&&y==this.y) {
			++res;
			return ;
		}
		help(x+1,y);
		help(x,y+1);
	}

}
